import math
n=499979

#先用一个比较笨的方法来求解
#就是两层循环，使用循环来求解,这种方式的时间复杂度是O(N^2),该方法会超时
def checkPrime(num):
    #从2->num-1 范围内
    for i in range(2,num):
        if num%i==0:
            return False
    return True

def countPrimes(n):
    count=0
    for i in range(2,n):
        if checkPrime(i):
            count+=1
    return count


#埃拉托斯特尼筛法
def countPrimes1(n):
    if n<=2:
        return 0
    primes=[True for _ in range(n+1)]
    primes[0]=False  #0不是素数
    primes[1]=False  #1不是素数
    count=n-2   #去掉不是素数的1 ，同时要求的是比n小的数里面的，所以n也不算，所以是n-2
    for i in range(2,n+1):
        if i<=n and primes[i]:
            j=2*i
            while j<n:
                if primes[j]:
                    primes[j]=False
                    count-=1
                j+=i
    return count

#进一步优化上面的算法
def countPrimes2(n):
    if n<=2:
        return 0
    primes=[True for _ in range(n+1)]
    i,sqrtn,count=3,math.sqrt(n),int(n/2)  #偶数一定不是质数
    while i<=sqrtn:
        #最小质因子一定小于等于开放数
        j=i*i
        while j<n:
            if primes[j]:
                count-=1
                primes[j]=False
            j+=2*i
        i+=2
        while i<=sqrtn and not primes[i]:
            i+=2
    return count
print(countPrimes2(n))







